package tree;

/**
 * Created by lizhenyu on 2019/9/18
 * description
 */
public class BinaryTree {

    private TreeNode root;

    public BinaryTree(int[] pre, int[] vin) {
        this.root = createTree_DLR_LDR(pre, vin);
    }
    /**
     * 构建二叉树
     *
     * @param pre 前序序列
     * @param vin 中序序列
     * @return
     */
    private TreeNode createTree_DLR_LDR(int[] pre, int[] vin) {
        // 空节点
        if(pre.length == 0) {
            return null;
        }
        // 确定根节点
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < vin.length; i++) {
            if(vin[i] == pre[0]) {
                // 递归构造左右子树
                root.left = createTree_DLR_LDR(cloneArray(pre, 1, i), cloneArray(vin, 0, i - 1));
                root.right = createTree_DLR_LDR(cloneArray(pre, i + 1, pre.length - 1), cloneArray(vin, i + 1, vin.length - 1));
                return root;
            }
        }
        return null;
    }

    /**
     * 二叉树节点类
     */
    class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode (int x) {
            this.value = x;
        }
    }

    /**
     * 获得树根节点
     *
     * @return
     */
    public TreeNode getTreeRoot() {
        return root;
    }

    /**
     * 前序遍历
     *
     * @param root
     */
    public void preOrderSequence(TreeNode root) {
        if (root != null) {
            System.out.print(root.value + " ");
            preOrderSequence(root.left);
            preOrderSequence(root.right);
        }
    }

    /**
     * 中序遍历
     *
     * @param root
     */
    public void midOrderSequence(TreeNode root) {
        if (root != null) {
            midOrderSequence(root.left);
            System.out.print(root.value + " ");
            midOrderSequence(root.right);
        }
    }

    /**
     * 后序遍历
     *
     * @param root
     */
    public void postOrderSequence(TreeNode root) {
        if (root != null) {
            postOrderSequence(root.left);
            postOrderSequence(root.right);
            System.out.print(root.value + " ");
        }
    }

    private int[] cloneArray(int[] arr, int left, int right) {
        int n = right - left + 1;
        int[] cla = new int[n];
        int i = 0;
        while (i < n) {
            cla[i] = arr[i + left];
            i++;
        }
        return cla;
    }
}



